package com.woldier.datastruacture.ch2.d10_tree.b_tree;

/**
 * description BTree
 * <p>
 * B树（B-Tree）结构是一种高效存储和查询数据的方法，它的历史可以追溯到1970年代早期。B树的发明人Rudolf Bayer和Edward M. McCreight分别发表了一篇论文介绍了B树。这篇论文是1972年发表于《ACM Transactions on Database Systems》中的，题目为"Organization and Maintenance of Large Ordered Indexes"。
 * <p>
 * 这篇论文提出了一种能够高效地维护大型有序索引的方法，这种方法的主要思想是将每个节点扩展成多个子节点，以减少查找所需的次数。B树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。
 * <p>
 * B树结构有很多变种和升级版，例如B+树，B*树和SB树等。这些变种和升级版本都基于B树的核心思想，通过调整B树的参数和结构，提高了B树在不同场景下的性能表现。
 * <p>
 * 总的来说，B树结构是一个非常重要的数据结构，为高效存储和查询大量数据提供了可靠的方法。它的历史可以追溯到上个世纪70年代，而且在今天仍然被广泛应用于各种场景。
 * <p>
 * 一棵 B-树具有以下性质
 * <p>
 * 特性1：每个节点 x 具有
 * <p>
 * * 属性 n，表示节点 x 中 key 的个数
 * * 属性 leaf，表示节点是否是叶子节点
 * * 节点 key 可以有多个，以升序存储
 * <p>
 * 特性2：每个非叶子节点中的孩子数是 n + 1、叶子节点没有孩子
 * <p>
 * 特性3：最小度数t（节点的孩子数称为度）和节点中键数量的关系如下：
 * <p>
 * 其中，当节点中键数量达到其最大值时，即 3、5、7 ... 2n-1，需要分裂
 * <p>
 * 特性4：叶子节点的深度都相同
 *
 * @author: woldier wong
 * @date: 2023/11/9$ 21:30$
 */
public class BTree {
    /**
    *
    * description B-Tree 的一个节点
    * @author: woldier wong
    * @date: 2023/11/10 9:41
    */
    static class Node{
        int t; //最小度数

        int keyNumber; //用于记录当前有多少个key是有效的
        int[] keys;  //节点key
        Node[] children; //孩子节点
        Node(int t){
            this.t = t;
            this.keys = new int[2*t-1];
            this.children = new Node[2*t];
        }
    }
}
